#include <stack>
#include <queue>
#include <iostream>

// 用两个栈实现一个队列
template <typename T>
class CQueue {
  public:
    void appendTail(const T& node);
    T deleteHead();
  private:
    std::stack<T> stack1;
    std::stack<T> stack2;
};

template <typename T>
void CQueue<T>::appendTail(const T& node) {
  stack1.push(node);
  std::cout << "new queue append tail element: " << node << std::endl;
}

template <typename T>
T CQueue<T>::deleteHead() {
  if (stack2.empty()) {
    while (!stack1.empty()) {
      auto node = stack1.top();
      stack1.pop();
      stack2.push(node);
    }
  }
  if (stack2.empty()) {
    std::cout << "new queue is empty." << std::endl;
    return 0;
  }
  auto node = stack2.top();
  stack2.pop();
  std::cout << "new queue delete head element: " << node << std::endl;
  return node;
}

// 用两个队列实现一个栈
template <typename T>
class CStack {
  public:
    void appendTail(const T& node);
    T deleteTail();
  private:
    std::queue<T> queue1;
    std::queue<T> queue2;
};

template <typename T>
void CStack<T>::appendTail(const T& node) {
  if (!queue1.empty()) {
    queue1.push(node);
  } else {
    queue2.push(node);
  }
  std::cout << "new stack append tail element: " << node << std::endl;
}

template <typename T>
T CStack<T>::deleteTail() {
  if (queue1.empty() && queue2.empty()) {
    std::cout << "new stack is empty." << std::endl;
    return 0;
  }
  if (queue1.empty() && !queue2.empty()) {
    swap(queue1, queue2);
    // queue1.swap(queue2);
  }
  while (queue1.size() != 1) {
    auto node = queue1.front();
    queue1.pop();
    queue2.push(node);
  }
  auto node = queue1.front();
  queue1.pop();
  std::cout << "new stack delete tail element: " << node << std::endl;
  return node;
}

void TestQueue() {
  std::cout << "Test new queue..." << std::endl;
  CQueue<int> queue;
  queue.appendTail(1);
  queue.appendTail(2);
  queue.appendTail(3);
  queue.deleteHead();
  queue.deleteHead();
  queue.appendTail(4);
  queue.deleteHead();
  queue.deleteHead();
  queue.deleteHead();
  queue.deleteHead();
  queue.appendTail(5);
  queue.appendTail(6);
  queue.deleteHead();
  std::cout << std::endl;
}

void TestStack() {
  std::cout << "Test new stack..." << std::endl;
  CStack<int> stack;
  stack.appendTail(1);
  stack.appendTail(2);
  stack.appendTail(3);
  stack.deleteTail();
  stack.deleteTail();
  stack.deleteTail();
  stack.deleteTail();
  stack.appendTail(1);
  stack.appendTail(2);
  stack.appendTail(3);
  stack.deleteTail();
  stack.deleteTail();
  stack.appendTail(1);
  stack.appendTail(2);
  stack.appendTail(3);
  stack.deleteTail();
  stack.deleteTail();
  stack.deleteTail();
  stack.deleteTail();
  stack.deleteTail();
  std::cout << std::endl;
}

int main() {
  TestQueue();
  TestStack();
  return 0;
}
